#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include "avltree.hpp"  // 你的 AVL 树头文件

using namespace STL;

void test_basic_operations() {
    std::cout << "=== 基础操作测试 ===" << std::endl;
    AvlTree<int, int> tree;
    
    // 测试插入
    tree.insert({5, 50});
    tree.insert({3, 30});
    tree.insert({7, 70});
    tree.insert({2, 20});
    tree.insert({4, 40});
    tree.insert({6, 60});
    tree.insert({8, 80});
    
    std::cout << "插入 5,3,7,2,4,6,8 后的树:" << std::endl;
    tree.print();
    std::cout << std::endl;
}

void test_avl_rotations() {
    std::cout << "=== AVL 旋转测试 ===" << std::endl;
    
    // 测试左旋 (LL情况)
    std::cout << "测试左旋 (LL情况):" << std::endl;
    AvlTree<int, int> tree1;
    tree1.insert({1, 10});
    tree1.insert({2, 20});
    tree1.insert({3, 30});
    tree1.print();
    std::cout << std::endl;
    
    // 测试右旋 (RR情况)
    std::cout << "测试右旋 (RR情况):" << std::endl;
    AvlTree<int, int> tree2;
    tree2.insert({3, 30});
    tree2.insert({2, 20});
    tree2.insert({1, 10});
    tree2.print();
    std::cout << std::endl;
    
    // 测试左右旋 (LR情况)
    std::cout << "测试左右旋 (LR情况):" << std::endl;
    AvlTree<int, int> tree3;
    tree3.insert({3, 30});
    tree3.insert({1, 10});
    tree3.insert({2, 20});
    tree3.print();
    std::cout << std::endl;
    
    // 测试右左旋 (RL情况)
    std::cout << "测试右左旋 (RL情况):" << std::endl;
    AvlTree<int, int> tree4;
    tree4.insert({1, 10});
    tree4.insert({3, 30});
    tree4.insert({2, 20});
    tree4.print();
    std::cout << std::endl;
}

void test_duplicate_keys() {
    std::cout << "=== 重复键测试 ===" << std::endl;
    AvlTree<int, int> tree;
    
    // 测试重复键 - 应该不会插入重复键
    tree.insert({5, 50});
    tree.insert({5, 55});  // 相同的键，不同的值
    tree.insert({5, 60});  // 相同的键，不同的值
    
    std::cout << "插入重复键 5 后的树:" << std::endl;
    tree.print();
    std::cout << "注意：AVL树通常不允许重复键，后面的插入应该被忽略" << std::endl;
    std::cout << std::endl;
}

void test_large_sequence() {
    std::cout << "=== 大序列测试 ===" << std::endl;
    AvlTree<int, int> tree;
    
    // 插入升序序列 - 测试右旋
    std::cout << "升序序列插入 (1-10):" << std::endl;
    for (int i = 1; i <= 10; ++i) {
        tree.insert({i, i * 10});
    }
    tree.print();
    std::cout << std::endl;
    
    AvlTree<int, int> tree2;
    // 插入降序序列 - 测试左旋
    std::cout << "降序序列插入 (10-1):" << std::endl;
    for (int i = 10; i >= 1; --i) {
        tree2.insert({i, i * 10});
    }
    tree2.print();
    std::cout << std::endl;
}

void test_random_sequence() {
    std::cout << "=== 随机序列测试 ===" << std::endl;
    AvlTree<int, int> tree;
    
    std::vector<int> numbers;
    for (int i = 1; i <= 20; ++i) {
        numbers.push_back(i);
    }
    
    // 随机打乱
    std::random_device rd;
    std::mt19937 g(rd());
    std::shuffle(numbers.begin(), numbers.end(), g);
    
    std::cout << "随机序列: ";
    for (int num : numbers) {
        std::cout << num << " ";
        tree.insert({num, num * 10});
    }
    std::cout << std::endl;
    
    tree.print();
    std::cout << std::endl;
}

void test_edge_cases() {
    std::cout << "=== 边界情况测试 ===" << std::endl;
    
    // 测试空树
    std::cout << "空树测试:" << std::endl;
    AvlTree<int, int> empty_tree;
    empty_tree.print();
    std::cout << std::endl;
    
    // 测试单节点
    std::cout << "单节点测试:" << std::endl;
    AvlTree<int, int> single_tree;
    single_tree.insert({1, 10});
    single_tree.print();
    std::cout << std::endl;
    
    // 测试两个节点
    std::cout << "两个节点测试:" << std::endl;
    AvlTree<int, int> two_tree;
    two_tree.insert({1, 10});
    two_tree.insert({2, 20});
    two_tree.print();
    std::cout << std::endl;
}

void test_complex_scenario() {
    std::cout << "=== 复杂场景测试 ===" << std::endl;
    AvlTree<int, int> tree;
    
    // 复杂插入序列，会触发多种旋转
    std::vector<int> sequence = {50, 25, 75, 15, 35, 65, 85, 10, 20, 30, 40, 60, 70, 80, 90};
    
    std::cout << "插入序列: ";
    for (int num : sequence) {
        std::cout << num << " ";
        tree.insert({num, num * 10});
    }
    std::cout << std::endl;
    
    tree.print();
    std::cout << std::endl;
}

int main() {
    std::cout << "AVL 树测试开始\n" << std::endl;
    
    test_basic_operations();
    test_avl_rotations();
    test_duplicate_keys();
    test_large_sequence();
    test_random_sequence();
    test_edge_cases();
    test_complex_scenario();
    
    std::cout << "所有测试完成!" << std::endl;
    return 0;
}